package com.note.feng.leetcode.nine;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;


public class Solution {

    /**
     * leetcode 9题：判断一个整数是否回文数
     * 一.题目描述：
     * 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒叙（从右向左）读都是一样的整数。
     * 示例1：
     * 输入：121
     * 输出：true
     * 示例2：
     * 输入：-121
     * 输出：false
     * 解释：从左向右读，为-121。从右向左读，为121-。因此它不是一个回文数。
     * 示例3：
     * 输入：10
     * 输出：false
     * 解释：从右向左读，为01。因此它不是一个回文数。
     * 进阶：
     * 你能不将整数转为字符串来解决这个问题吗？
     * 英文描述：
     * Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
     */
    /**
     * 具体思路为：比如x=121这个数，先设立一个变量res=0,
     * 当x>0时不断对x取余，121%10=1,然后令res=121%10+10res=1，
     * 同时对x不断除10取整，保证取到倒数上一位数, res=12%10+110 = 12,
     * 最后 res=1%10+12*10=121。
     * @param x
     * @return
     */
    public boolean isPalindrome(int x){
        if(x < 0) return false;
        int temp = x;
        int res = 0;
        while(temp != 0){
            res = temp % 10 + res * 10;
            temp /= 10;
        }
        return res == x;
    }

    /**
     * 解法二：回文在中间对折后，两边应该是一样的，所以在解法一的基础上，
     * 只要反转后一半，再与前一半对比是否一样就可以了
     * @param x
     * @return
     */
    public boolean isPalindrome2(int x){
        if(x < 0) return false;
        int res = 0;
        while(x > res){
            res = x % 10 + res * 10;
            x /= 10;
        }
        return res == x || res / 10 == x;
    }

    /**
     * 942:增减字符串匹配
     * 由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表示为长度为 n 的字符串 s ，其中:
     *
     * 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I' 
     * 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D' 
     * 给定一个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中 任何一个 。
     *
     * 示例 1：
     *
     * 输入：s = "IDID"
     * 输出：[0,4,1,3,2]
     * 示例 2：
     *
     * 输入：s = "III"
     * 输出：[0,1,2,3]
     * 示例 3：
     *
     * 输入：s = "DDI"
     * 输出：[3,2,0,1]
     *
     * 提示：
     *
     * 1 <= s.length <= 105
     * s 只包含字符 "I" 或 "D"
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/di-string-match
     * @param s
     * @return
     */
    /**
     * 贪心思想：
     * 因为本题用到了贪心算法所以先来了解一下「贪心算法」的问题需要满足的条件：
     *
     * 最优子结构：规模较大的问题的解由规模较小的子问题的解组成，规模较大的问题的解只由其中一个规模较小的子问题的解决定；
     * 无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
     * 贪心选择性质：从局部最优解可以得到全局最优解。
     * 综上可得：贪心算法就是做出当前状态下的最优选择认为就可以解决问题。
     * 思路分析：
     * 因为 I 和 D 决定了 前后位置的大小关系，按照贪心算法的思想，每次根据 I 或 D 选取 T 中最小或最大的数字，如果已经使用过的去掉，从没用过的里面选。具体步骤如下：
     *
     * 用两个指针来保存当前 T 中的 最大值max 和最小值min ；
     * 遍历字符串
     * 如果 s[i]=‘I’，那么令 result[i] 为剩余数字中的最小数；
     * 如果 s[i]=‘D’，那么令 result[i] 为剩余数字中的最大数。
     * 最后一个数，填入 result[n] 中；
     * 返回结果 result。
     *
     */
    public int[] diStringMatch(String s) {
        int length = s.length();
        int [] res = new int[length + 1];
        int left = 0;
        int right = length;
        for(int i = 0; i < length; i++){
            res[i] = s.charAt(i) == 'I' ? left ++ : right --;
        }
        res[length] = left;
        return res;
    }

    /**
     * 1、两数之和
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
     *
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     *
     * 你可以按任意顺序返回答案。
     *
     *
     * 示例 1：
     *
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[0,1]
     * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     * 示例 2：
     *
     * 输入：nums = [3,2,4], target = 6
     * 输出：[1,2]
     * 示例 3：
     *
     * 输入：nums = [3,3], target = 6
     * 输出：[0,1]
     *
     * 提示：
     *
     * 2 <= nums.length <= 104
     * -109 <= nums[i] <= 109
     * -109 <= target <= 109
     * 只会存在一个有效答案
     * 进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/two-sum
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        /**
         * 解法一：哈希表
         *
         *算法描述
         * 在哈希表1算法中，拷贝了完整的原数组到哈希表中，在哈希表中查找target - nums[i]时，会基于完整的数据查找。可以不直接拷贝原数组到哈希表中，而是在遍历nums查找哈希表时，找不到再put(K,V)，找到则立即返回结果。采用这样的方式能够节省哈希表的空间，且减少空间的同时也削减了计算哈希值的耗时。
         *
         * 时空复杂度
         * 时间复杂度取决于遍历原数组耗时，为O(n)。使用了哈希表存储数组内容，空间复杂度O(n)。
         *
         */
//        int length = nums.length;
//        if(length < 2){
//            return new int[] {0, 1};
//        }
//        Map<Integer, Integer> map = new HashMap<>();
//        for(int i = 0; i < length; i++){
//            int n = target - nums[i];
//            if(map.containsKey(n)){
//                return new int[] {map.get(n), i};
//            }
//            map.put(nums[i], i);
//        }
//        return null;

        /**
         * 解法二： 哈希表
         *
         * 算法描述
         * 在解法一的基础上仍可改进，即每次在哈希表中搜索补数时，设置left和right两个指针，
         * 一次搜索nums中左右两端的元素的补数，可以得到耗时0ms的效果。
         *
         * 时空复杂度
         * 时间复杂度取决于遍历原数组耗时，为O(n)。使用了哈希表存储数组内容，空间复杂度O(n)
         */
        int length = nums.length;
        if(length <= 2){
            return new int[] {0, 1};
        }
        Map<Integer, Integer> map = new HashMap<>();
        int left = 0,right = length - 1;
        while(left <= right){
            int n1 = target - nums[left];
            if(map.containsKey(n1)){
                return new int[] {map.get(n1), left};
            }else{
                map.put(nums[left], left ++);
            }
            int n2 = target - nums[right];
            if(map.containsKey(n2)){
                return new int[] {map.get(n2), right};
            }else{
                map.put(nums[right], right --);
            }
        }
        return null;

    }

    /**
     * 13.罗马数字转整数
     *
     * 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
     *
     * 字符          数值
     * I             1
     * V             5
     * X             10
     * L             50
     * C             100
     * D             500
     * M             1000
     * 例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做  XXVII, 即为 XX + V + II 。
     *
     * 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。
     * 数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。
     * 这个特殊的规则只适用于以下六种情况：
     *
     * I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
     * X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。 
     * C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
     * 给定一个罗马数字，将其转换成整数。
     *
     *
     * 示例 1:
     *
     * 输入: s = "III"
     * 输出: 3
     * 示例 2:
     *
     * 输入: s = "IV"
     * 输出: 4
     * 示例 3:
     *
     * 输入: s = "IX"
     * 输出: 9
     * 示例 4:
     *
     * 输入: s = "LVIII"
     * 输出: 58
     * 解释: L = 50, V= 5, III = 3.
     * 示例 5:
     *
     * 输入: s = "MCMXCIV"
     * 输出: 1994
     * 解释: M = 1000, CM = 900, XC = 90, IV = 4.
     *  
     *
     * 提示：
     *
     * 1 <= s.length <= 15
     * s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
     * 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
     * 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
     * IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
     * 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/roman-to-integer
     * @param s
     * @return
     */
    /**
     * 解法：
     * 字符串从左向右遍历，如果左边比右边小，则减去左边，否则加上左边，最后再加上最右边的值
     * @param s
     * @return
     */
    public int romanToInt(String s) {
        int res = 0;
        int pre = getIntValues(s.charAt(0));
        for(int i = 1; i < s.length(); i++){
            int num = getIntValues(s.charAt(i));
            if(pre < num){
                res -= pre;
            }else{
                res += pre;
            }
            pre = num;
        }
        return res + pre;
    }
    private int getIntValues(Character character){
        switch (character){
            case 'I':
               return 1;
            case 'V':
                return 5;
            case 'X':
                return 10;
            case 'L':
                return 50;
            case 'C':
                return 100;
            case 'D':
                return 500;
            case 'M':
                return 1000;
        }
        return 0;
    }

    /**
     * 14 最长公共前缀
     *
     * 编写一个函数来查找字符串数组中的最长公共前缀。
     *
     * 如果不存在公共前缀，返回空字符串 ""。
     *
     * 示例 1：
     *
     * 输入：strs = ["flower","flow","flight"]
     * 输出："fl"
     * 示例 2：
     *
     * 输入：strs = ["dog","racecar","car"]
     * 输出：""
     * 解释：输入不存在公共前缀。
     *  
     *
     * 提示：
     *
     * 1 <= strs.length <= 200
     * 0 <= strs[i].length <= 200
     * strs[i] 仅由小写英文字母组成
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/longest-common-prefix
     *
     * @param strs
     * @return
     */
    /**
     * 解法：
     * 纵向扫描：
     * 先找出最短字符串的长度，这就是最大公共前缀的最大长度。
     * 从左向右依次遍历所有字符串，若相同下标对应的字符相同，继续遍历，否则0到当前下标-1就是最大公共前缀
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if(strs == null){
            return "";
        }
        if(strs.length == 1){
            return strs[0];
        }
        int minLen = strs[0].length();
        for(String str : strs){
            minLen = str.length() > minLen ? minLen : str.length();
        }
        String pre = "";
        for(int i = 0; i < minLen; i++){
            char ch = strs[0].charAt(i);
            for(String str : strs){
                if(ch != str.charAt(i)){
                    return pre;
                }
            }
            pre += ch;
        }
        return pre;
    }

    /**
     * 解法二：
     * 随机找一个字符串，遍历对比是否是最长公共前缀，若不是，该字符串长度减一，再遍历
     * @param strs
     * @return
     */
    public String longestCommonPrefix2(String[] strs) {
        if(strs == null || strs.length == 0){
            return "";
        }
        if(strs.length == 1){
            return strs[0];
        }
        String pre = strs[0];
        for (String str : strs){
            while(str.indexOf(pre) != 0){
                pre = pre.substring(0, pre.length() - 1);
                if(pre.length() == 0){
                    return pre;
                }
            }
        }
        return pre;
    }

    /**
     * 20. 有效的括号
     *
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     *  
     *
     * 示例 1：
     *
     * 输入：s = "()"
     * 输出：true
     * 示例 2：
     *
     * 输入：s = "()[]{}"
     * 输出：true
     * 示例 3：
     *
     * 输入：s = "(]"
     * 输出：false
     * 示例 4：
     *
     * 输入：s = "([)]"
     * 输出：false
     * 示例 5：
     *
     * 输入：s = "{[]}"
     * 输出：true
     *  
     *
     * 提示：
     *
     * 1 <= s.length <= 104
     * s 仅由括号 '()[]{}' 组成
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/valid-parentheses
     * @param s
     * @return
     */
    /**
     * 解法：
     * 借用stack，如果是左括号就入栈，否则出栈，与当前括号，对比，不是一对，返回false；
     * 若字符串遍历结束，stack不为空，返回false
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        if(s.length() % 2 != 0){
            return false;
        }
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{'){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }
                char c = stack.pop();
                if(ch == ')' && c != '('){
                    return false;
                }
                if(ch == ']' && c != '['){
                    return false;
                }
                if(ch == '}' && c != '{'){
                    return false;
                }
            }
        }
        return stack.empty();
    }

    /**
     * 26 删除有序数组中的重复项
     * 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
     *
     * 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
     *
     * 将最终结果插入 nums 的前 k 个位置后返回 k 。
     *
     * 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     *
     * 判题标准:
     *
     * 系统会用下面的代码来测试你的题解:
     *
     * int[] nums = [...]; // 输入数组
     * int[] expectedNums = [...]; // 长度正确的期望答案
     *
     * int k = removeDuplicates(nums); // 调用
     *
     * assert k == expectedNums.length;
     * for (int i = 0; i < k; i++) {
     *     assert nums[i] == expectedNums[i];
     * }
     * 如果所有断言都通过，那么您的题解将被 通过。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：nums = [1,1,2]
     * 输出：2, nums = [1,2,_]
     * 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
     * 示例 2：
     *
     * 输入：nums = [0,0,1,1,1,2,2,3,3,4]
     * 输出：5, nums = [0,1,2,3,4]
     * 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
     *  
     *
     * 提示：
     *
     * 0 <= nums.length <= 3 * 104
     * -104 <= nums[i] <= 104
     * nums 已按 升序 排列
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array
     * @param nums
     * @return
     */
    /**
     * 解法：
     * 双指针：初始左指针表示下标0，右指针表示下标1，左指针与右指针存在两种情况：
     * 1、左指针等于右指针；
     * 2、左指针小于右指针；
     * 若为情况1，左指针不变，右指针右移一位，直到为情况2或者数组遍历结束；
     * 若为情况2，左指针左移一位，同时左指针赋值为右指针，右指针右移一位；
     * 最终，左指针代表当前数组非重复数据的位置，返回左指针+1
     * @param nums
     * @return
     */
    public int removeDuplicates(int[] nums) {
        int length = nums.length;
        if(length == 0 || length == 1){
            return length;
        }
        int left = 0, right = 1;
        while(length > right){
            if(nums[left] != nums[right]){
                left ++;
                nums[left] = nums[right];
                right ++;
            }else{
                right ++;
            }
        }
        return left + 1;
    }

    /**
     * 27 移除元素
     * 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
     *
     * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
     *
     * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
     *
     * 说明:
     *
     * 为什么返回数值是整数，但输出的答案是数组呢?
     *
     * 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     *
     * 你可以想象内部操作如下:
     *
     * // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
     * int len = removeElement(nums, val);
     *
     * // 在函数里修改输入数组对于调用者是可见的。
     * // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
     * for (int i = 0; i < len; i++) {
     *     print(nums[i]);
     * }
     *  
     *
     * 示例 1：
     *
     * 输入：nums = [3,2,2,3], val = 3
     * 输出：2, nums = [2,2]
     * 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。
     * 例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
     * 示例 2：
     *
     * 输入：nums = [0,1,2,2,3,0,4,2], val = 2
     * 输出：5, nums = [0,1,4,0,3]
     * 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。
     * 你不需要考虑数组中超出新长度后面的元素。
     *  
     * 提示：
     *
     * 0 <= nums.length <= 100
     * 0 <= nums[i] <= 50
     * 0 <= val <= 100
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/remove-element
     * @param nums
     * @param val
     * @return
     */
    /**
     * 解法：
     * 双指针：左右双指针，初始均为0，遍历数组，只有两种情况：
     * 1、当前元素不等于指定值；
     * 2、当前元素等于指定值；
     * 若为情况1，左指针元素等于右指针元素，左右指针均右移一位；
     * 若为情况2，右指针右移一位；
     * 最终左指针即是移除指定值后数组的长度
     * @param nums
     * @param val
     * @return
     */
    public int removeElement(int[] nums, int val) {
        int length = nums.length;
        if(length == 0){
            return 0;
        }
        int left = 0, right = 0;
        while(length > right){
            if(nums[right] == val){
                right ++;
            }else{
                nums[left ++] = nums[right ++];
            }
        }
        return left;
    }

    /**
     * 28 实现strStr
     * 实现 strStr() 函数。
     *
     * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。
     * 如果不存在，则返回  -1 。
     *
     * 说明：
     *
     * 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
     *
     * 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及
     * Java 的 indexOf() 定义相符。
     *
     * 示例 1：
     *
     * 输入：haystack = "hello", needle = "ll"
     * 输出：2
     * 示例 2：
     *
     * 输入：haystack = "aaaaa", needle = "bba"
     * 输出：-1
     * 示例 3：
     *
     * 输入：haystack = "", needle = ""
     * 输出：0
     *  
     * 提示：
     *
     * 1 <= haystack.length, needle.length <= 104
     * haystack 和 needle 仅由小写英文字符组成
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/implement-strstr
     * @param haystack
     * @param needle
     * @return
     */
    /**
     * 解法：
     * 暴力破解：
     * 枚举haystack字符串中每个字符为起点的needle的长度的字符串，进行匹配，
     * 成功，返回本次匹配的起点，
     * 最终失败，返回-1
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {
        int n = needle.length();
        int length = haystack.length();
        if(n == 0){
            return 0;
        }
        if(n > length) {
            return -1;
        }
        for(int i = 0; i <= length - n; i ++){
            int a = i, b = 0;
            while(b < n && haystack.charAt(a) == needle.charAt(b)){
                a ++;
                b ++;
            }
            if(b == n){
                return i;
            }
        }
        return -1;
    }

    /**
     * 35 搜索插入位置
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     *
     * 请必须使用时间复杂度为 O(log n) 的算法。
     *
     * 示例 1:
     *
     * 输入: nums = [1,3,5,6], target = 5
     * 输出: 2
     * 示例 2:
     *
     * 输入: nums = [1,3,5,6], target = 2
     * 输出: 1
     * 示例 3:
     *
     * 输入: nums = [1,3,5,6], target = 7
     * 输出: 4
     *  
     * 提示:
     *
     * 1 <= nums.length <= 104
     * -104 <= nums[i] <= 104
     * nums 为 无重复元素 的 升序 排列数组
     * -104 <= target <= 104
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/search-insert-position
     * @param nums
     * @param target
     * @return
     */
    /**
     * 解法：
     * 二分法：
     * (right - left) / 2 + left ,是防止溢出
     * 每次循环区间都在变小，会出现3种情况：
     * 1、等于target，直接返回n;
     * 2、小于target，说明应该在区间[n + 1,right]内
     * 3、大于target，说明应该在区间[left, n - 1]内
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        int left = 0, right = len - 1;
        while(left <= right){
            int n = (right - left) / 2 + left;
            if(nums[n] == target){
                return n;
            }else if(nums[n] < target){
                 left = n + 1;
            }else{
                right = n -1;
            }
        }
        return left;
    }

    /**
     * 53 最大子数组和
     * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
     *
     * 子数组 是数组中的一个连续部分。
     *
     * 示例 1：
     *
     * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出：6
     * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
     * 示例 2：
     *
     * 输入：nums = [1]
     * 输出：1
     * 示例 3：
     *
     * 输入：nums = [5,4,-1,7,8]
     * 输出：23
     *
     * 提示：
     *
     * 1 <= nums.length <= 105
     * -104 <= nums[i] <= 104
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/maximum-subarray
     * @param nums
     * @return
     */
    /**
     * 解法：
     * 动态规划：
     * 1、定义状态（定义子问题）
     *  sum[i]：表示以nums[i]结尾的连续子数组的最大和
     *  【连续】 和 【结尾】  是关键词
     * 2、状态转移方程（描述子问题之间的联系）
     *  根据状态的定义，由于nums[i]一定会被选取，并且以nums[i]结尾的连续子数组与
     *  以nums[i - 1]结尾的连续子数组，只相差一个元素nums[i]；
     *  假设数组nums的值都大于0，那么一定有sum[i] = sum[i - 1] + nums[i];
     *  可是：sum[i]有可能是负数，会有以下2中情况：
     *  2.1、sum[i - 1]大于0，那么可以把nums[i]直接接在sum[i - 1]表示的那个数组的后面，得到和更大的连续子数组；
     *  2.2、sum[i - 1]小于0，那么nums[i] 加上sum[i - 1]，值不会变大，于是sum[i] 另起炉灶，此时单独的一个nums[i],就是sum[i];
     *  以上两种情况的最大值就是sum[i]的值，
     * 3、边界：
     *  当nums只有一个值时，最大连续子数组的和就是nums[0],所有sum[0] = nums[0]
     * 4、遍历完nums之后，sum数组的值就初始化完成，sum数组中的最大的元素就是问题的解。
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        //表示以数组nums下标i为结尾的连续子数组的最大和
        int [] sum = new int[len];
        sum[0] = nums[0];
        for(int i = 1; i < len; i++){
            if(sum[i - 1] > 0){
                sum[i] = sum[i - 1] + nums[i];
            }else{
                sum[i] = nums[i];
            }
        }
        int res = sum[0];
        for(int i = 1; i < len; i++){
            res = res > sum[i] ? res : sum[i];
        }
        return res;
    }

    /**
     * 58 最后一个单词的长度
     * 给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
     *
     * 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
     *
     * 示例 1：
     *
     * 输入：s = "Hello World"
     * 输出：5
     * 解释：最后一个单词是“World”，长度为5。
     * 示例 2：
     *
     * 输入：s = "   fly me   to   the moon  "
     * 输出：4
     * 解释：最后一个单词是“moon”，长度为4。
     * 示例 3：
     *
     * 输入：s = "luffy is still joyboy"
     * 输出：6
     * 解释：最后一个单词是长度为6的“joyboy”。
     *  
     * 提示：
     *
     * 1 <= s.length <= 104
     * s 仅有英文字母和空格 ' ' 组成
     * s 中至少存在一个单词
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/length-of-last-word
     * @param s
     * @return
     */
    /**
     * 解法：
     * 反向遍历，遇到字母，size++，遇到空格，若size>0,返回size，都在继续遍历
     * @param s
     * @return
     */
    public int lengthOfLastWord(String s) {
        int len = s.length();
        int size = 0;
        for(int i = len - 1; i >= 0; i --){
            if(s.charAt(i) != ' '){
                size ++;
            }else{
                if(size > 0){
                    return size;
                }
            }
        }
        return size;
    }

    /**
     * 66 加一
     * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
     *
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     *
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     *
     * 示例 1：
     *
     * 输入：digits = [1,2,3]
     * 输出：[1,2,4]
     * 解释：输入数组表示数字 123。
     * 示例 2：
     *
     * 输入：digits = [4,3,2,1]
     * 输出：[4,3,2,2]
     * 解释：输入数组表示数字 4321。
     * 示例 3：
     *
     * 输入：digits = [0]
     * 输出：[1]
     *
     * 提示：
     *
     * 1 <= digits.length <= 100
     * 0 <= digits[i] <= 9
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/plus-one
     * @param digits
     * @return
     */
    /**
     * 解法：
     * 反向遍历：最后一个元素+1，若和大于9，则该位置赋值为和取余10，
     * 继续遍历，直到和小于等于9，该元素赋值为和，并返回数组；
     * 若数组遍历完成，仍没有返回，说明数组的每一个元素都是9，
     * 新建一个数组，长度为原数组长度+1，首位设置为1，其他位为0，返回新数组。
     * @param digits
     * @return
     */
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        for(int i = len - 1; i >= 0; i --){
            int sum = digits[i] + 1;
            if(sum > 9){
                digits[i] = sum % 10;
            }else{
                digits[i] = sum;
                return digits;
            }
        }
        int [] res = new int[len + 1];
        res[0] = 1;
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
//        System.out.println(solution.isPalindrome(123321));
//        System.out.println(Arrays.toString(solution.diStringMatch("IDID")));
//        System.out.println(solution.romanToInt("MCMXCIV"));
//        System.out.println(solution.isValid("()[]{}"));
        System.out.println(solution.strStr("hello", "o"));
    }

}
